1. Field of the Invention
The present invention relates to a method of extracting ridge and valley lines from three-dimensional point data.
2. Description of the Related Art
Recently, as a result of rapid development of a three-dimensional range scanning system, it has been common to have to process very complicated three-dimensional models obtained from the system. Also, by using such a three-dimensional range scanning system, even an actual object with a complicated shape can be measured quickly, accurately, and automatically. Three-dimensional models obtained by such measurement are used in various application fields, such as medical images, animations, games, and reverse engineering.
Various fields such as three-dimensional model visualization, geometric modeling and computer graphics, require that ridge and valley lines be extracted from a point set. This is because such extraction plays an important part in areas such as mesh reconstruction, shape analysis, and model division.
Conventionally, a model shape feature has been extracted to improve the visualization of a point set and facilitate the process of transforming a point set into a triangular mesh. Extraction of feature lines from a point set is closely related to mesh surface reconstruction. This is because such a mesh-surface reconstruction process is very sensitive to the features of a model. Therefore, extraction of feature lines from an undefined point set with unknown connection information may be used as a pre-processing step of mesh reconstruction.
Conventional techniques of directly extracting ridge and valley lines from three-dimensional point data obtained through a three-dimensional range scanning system requires a lot of time, and in addition, often has poor rendering results. Also, since extracting ridge and valley lines from three-dimensional point data requires many steps, such a technique is complicated and usually has a very high time complexity. In addition, there is a problem in that thinly extracted feature portions cannot be easily found.